package j2025.j01;

import java.lang.reflect.MalformedParameterizedTypeException;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @Author 猫大仙
 */
public class j0129 {

 /**
  * 347. 前 K 个高频元素
  * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
  * 你可以按 任意顺序 返回答案。
  *
  *
  * @param nums
  * @param k
  * @return
  */
     public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> maps = new HashMap<>();
        for(int i = 0;i<nums.length;i++){
         maps.put(nums[i],maps.getOrDefault(nums[i],0)+1);
        }
        PriorityQueue<int[]> q = new PriorityQueue<>((int[] a,int[] b)->{
            return a[1]-b[1];
        });
        for(Map.Entry<Integer,Integer> map:maps.entrySet()){
             int key = map.getKey();
             int value = map.getValue();
             if(q.size()==k){
                 int tmp = q.peek()[1];
                 if(tmp < value){
                     q.poll();
                     q.offer(new int[]{key,value});
                 }
             }else {
                 q.offer(new int[]{key,value});
             }
        }
        int[] ret = new int[k];
        for(int i = 0;i<k;i++){
            ret[i] = q.poll()[0];
        }
        return ret;
     }
}

/**
 * 208. 实现 Trie (前缀树)
 * Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，
 * 用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
 *
 * 请你实现 Trie 类：
 *
 * Trie() 初始化前缀树对象。
 * void insert(String word) 向前缀树中插入字符串 word 。
 * boolean search(String word) 如果字符串 word 在前缀树中，
 * 返回 true（即，在检索之前已经插入）；否则，返回 false 。
 * boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，
 * 返回 true ；否则，返回 false 。
 */
class Trie {
    private Trie[] children;
    private boolean isEnd;
    public Trie() {
         isEnd = false;
         children = new Trie[26];
    }

    public void insert(String word) {
          Trie node = this;
          for(char ch:word.toCharArray()){
              if(node.children[ch-'a']==null){
                  node.children[ch-'a'] = new Trie();
              }
              node = node.children[ch-'a'];
          }
          node.isEnd = true;
    }

    public boolean search(String word) {
         Trie node = this;
         for(char ch:word.toCharArray()){
             node =  node.children[ch-'a'];
             if(node == null){
                return false;
             }
         }
         return node.isEnd;
    }

    public boolean startsWith(String prefix) {
          Trie node = this;
          for(char ch:prefix.toCharArray()){
           node =  node.children[ch-'a'];
           if(node == null){
            return false;
           }
          }
          return true;
    }
}
